COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.DEVICE XGP
C00004 00003	5↓_A Meaningful Question_↓*
C00008 00004	5↓_Special Case: n = 2↑a3↑b_↓*
C00014 00005	5↓_Special Case: n = 2↑a3↑b5↑c_↓*
C00019 00006	5↓_General Case_↓*
C00023 00007	5↓_An even stronger claim_↓*
C00027 00008	5↓_New Questions and Tasks_↓*
C00030 ENDMK
C⊗;
.DEVICE XGP

.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4  "BASI30"
.FONT 5  "BDR40"
.FONT 6  "NGR25"
.FONT 7  "NGR20"
.FONT 8 "SUP"
.FONT 9 "SUB"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.PAGE FRAME 54 HIGH 80 WIDE
.AREA TEXT LINES 4 TO 53
.COUNT PAGE PRINTING "1"
.TABBREAK
.ODDLEFTBORDER←EVENLEFTBORDER←1000
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠"  ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff"  ⊂ IF THISFONT ≤ 4 THEN "≥"  ELSE "fαf" ⊃;
.AT "fi"  ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl"  ⊂ IF THISFONT ≤ 4 THEN "∨"  ELSE "fαl" ⊃;
.MACRO B ⊂ BEGIN NOFILL PREFACE 0 FLUSH LEFT VERBATIM GROUP ⊃
.MACRO B1 ⊂ BEGIN PREFACE 0 INDENT 0 SINGLE SPACE ⊃
.MACRO E ⊂ APART END  SELECT 1 ⊃
.MACRO FAD ⊂ FILL ADJUST DOUBLE SPACE PREFACE 2 ⊃
.MACRO FAS ⊂ FILL ADJUST SINGLE SPACE PREFACE 1 ⊃
.FAS
.PAGE←0
.NEXT PAGE
.INDENT 0
.TURN OFF "{∞→}"   
.GROUP SKIP 1
.BEGIN CENTER  PREFACE 0

⊗5↓_Maximally-Divisible Numbers_↓⊗*





⊗5Mathematical Concepts Developed by⊗*

D. Lenat
R. Davis
and the "⊗4Automated Mathematician⊗*" computer program



.END
.SELECT 1
.EVERY HEADING(⊗7Douglas B. Lenat⊗*,⊗4↓_Automated Mathematician_↓⊗* results,⊗7Maximally-Divisible Numbers      page   {PAGE}⊗*)

⊗5↓_A Meaningful Question_↓⊗*

We begin by asking the question, "What is the ⊗4converse⊗* concept to prime
numbers?"  
If we define "primeness" to mean that a natural number has as few divisors
as possible (namely, just two of them: 1 and itself), then the converse kind
of number would be one which
had an abnormally ⊗4large⊗* number of divisors.

One could consider the following set of maximally-divisible numbers:

.B1

⊗6M = {xεN↑+ | (∀y<x) ( d(y) < d(x) ) }⊗*

.END

In words, this says that M is the set of all positive integers satisfying
the property that every smaller number has fewer divisors.
That is, we throw into the set M a number x if (and only if) it has more
divisors than any smaller number.
So 1 gets thrown in (the smallest number with 1 divisor),
2 (having 2 divisors), 4 (3 divisors, namely 1, 2, and 4), 6 (4 divisors),
12 (6 divisors), etc.
Another way to specify M is as the set containing (for all n) the smallest
number having at least n divisors.
Notice that we are ⊗4not⊗* going to include "the smallest number with
⊗4precisely⊗* 5 divisors", since this number (2↑4 = 16) is bigger than
12 (which has 6 divisors).

One of the questions at the heart of our study is "Given d, what is the
smallest number with at least d divisors?"


How can we even start on this question? The most powerful tool we have is
the following combinatorially-proved theorem:

.ONCE PREFACE 0 FLUSH LEFT
⊗5(T1)⊗*  If we write n as 2↑a↑[⊗71⊗*]3↑a↑[⊗72⊗*...]p↓k↑a↑[⊗7k⊗*], then d(n) = (a↓1+1)(a↓2+1)...(a↓[⊗7k⊗*]+1).

Our central question could be answered if we could somehow invert this
formula into one which expressed n as a function of d, and then found the
minima of that function n(d).
Coupled with the knowledge that each number can be factored uniquely into
prime factors, T1 provides a closed-form way of manipulating d(n).
That is, n is really a function of the sequence of exponents when written
as 2↑a⊗81⊗*3↑a⊗82⊗*..., so we can consider n = n(a↓1, a↓2,...).
Then T1 is really a way of expressing d(n) = d(a↓1, a↓2,...).

.SKIP TO COLUMN 1

⊗5↓_Special Case: n = 2↑a3↑b_↓⊗*

Let's consider a special case. We'll restrict our attention to numbers n which
are of the form 2↑a3↑b. So T1 says that d(n)=(a+1)(b+1).
Consider fixing d, and asking how n varies with a and b.
Notice that we are now saying that (a+1)(b+1)=d=constant.
So we can say that (b+1)=d/(a+1), so b=(d/(a+1))-1.
So our number n is really 2⊗8a⊗*3⊗8[(d/(a+1))-1]⊗*.
Aha! This is an expression for n simply as a function of a.
We can use calculus to find the minima of this function. That will correspond
to the optimal exponent a, from which we can compute the optimal b.

.SELECT 1

.B1

⊗4d⊗*n/⊗4d⊗*a  =  2↑a(3↑b(-d/(a+1)↑2)log(3)) + 3↑[(d/(a+1))-1](2↑alog(2))

    = [(a+1)log(2)  -  (b+1)log(3)](n/(a+1)).

.E

This is zero when (a+1)log(2) = (b+1)log(3).    

So we have two equations now:
.B1

(a+1) = (b+1)log(3)/log(2)

(a+1) = d/(b+1)
.E

Together they say that 
(b+1)log(3)/log(2)  =  d/(b+1),
from which we derive (b+1)↑2 = log(2)d/log(3). Substituting this back in, we
also get that (a+1)↑2 = log(3)d/log(2).

If real-valued exponents were allowed, our optimal n(d) would be
⊗52⊗*↑[SQRT]⊗8[log(3)d/log(2)]⊗*⊗53⊗*↑[SQRT]⊗8[log(2)d/log(3)]⊗*.

Three observations we can make from intuition -- and justify from reality -- are
(i) this optimal real value is better than (i.e., ⊗6≤⊗*) any integral n 
(divisible only by 2 and 3)
with at least d divisors,
(ii) the ideal n is very close to the best such integral n,
(iii) the best such integral n will have exponents a and b which are close to
our theoretical real-valued "ideal" a and b.

For example, if we choose to ask for a number with at least 8 divisors,
our theoretical values for a and b are about 2.6 and 1.2; the ideal n is
then about 23. In actuality, the first number with 8 or more divisors is
24, and it is factored into 2⊗83⊗*3⊗81⊗* (i.e., the best integral values
for a and b are 3 and 1, respectively).

⊗5↓_Special Case: n = 2↑a3↑b5↑c_↓⊗*

.SELECT 1

Let's consider a second special case. 
We'll restrict our attention to numbers n which
are of the form 2↑a3↑b5↑c. So T1 says that d(n)=(a+1)(b+1)(c+1).
Consider fixing d, and asking how n varies with a, b, and c.
Notice that we are now saying that (a+1)(b+1)(c+1)=d=constant.
So we can say that (c+1)=d/(a+1)(b+1), so c=(d/(a+1)(b+1))-1.
So our number n is really 2⊗8a⊗*3⊗8b⊗*5⊗8[(d/(a+1)(b+1))-1]⊗*.

Viewing c as a function of a and b, we can compute the differential

.B1 SELECT 1

⊗4d⊗*c = ⊗4d⊗*(d/(a+1)(b+1)) 

 =  d [⊗4d⊗*(1/(a+1)(b+1))] 

 = (d)[(1/(a+1))(-1/(b+1)↑2)⊗4d⊗*b + (1/(b+1))(-1/(a+1)↑2)⊗4d⊗*a]

 = (-(c+1)/(b+1))⊗4d⊗*b + (-(c+1)/(a+1))⊗4d⊗*a

.E SKIP TO COLUMN 1

We want to minimize this function n=n(a,b). It will turn out to be
easier to find the minima of log(n), viewed as a function of a and b.
Now log(n) = log(2)a + log(3)b + log(5)c.
So the differential ⊗4d⊗*n = log(2)⊗4d⊗*a + log(3)⊗4d⊗*b + log(5)⊗4d⊗*c.
Substituting in the value we obtained for ⊗4d⊗*c, we get

.B1

⊗4d⊗*n = log(2)⊗4d⊗*a + log(3)⊗4d⊗*b + log(5)[(-(c+1)/(b+1))⊗4d⊗*b + (-(c+1)/(a+1))⊗4d⊗*a]

= [log(2)-(c+1)log(5)/(a+1)]⊗4d⊗*a + [log(3)-(c+1)log(5)/(b+1)]⊗4d⊗*b

.E

One nice way to make this identically zero is if the coefficients of
⊗4d⊗*a and ⊗4d⊗*b become zero. That is, n will have minima when
both log(2) = (c+1)log(5)/(a+1) and log(3) = (c+1)log(5)/(b+1) are true.
That is, when (a+1)log(2) = (b+1)log(3) = (c+1)log(5).

This is a generalization of the earlier result that minima occur when
(a+1)log(2) = (b+1)log(3).
We can easily see that the general pattern of the constraints are:
(a↓i+1)/(a↓j+1) = log(p↓j)/log(p↓i),

What are the explicit formulae for the exponents in the k=3 case?
We can solve for them in terms of d by using T1.
Namely,

.B1

(a+1)(b+1)(c+1) = d

(a+1) = (c+1)log(5)/log(2)

(b+1) = (c+1)log(5)/log(3)

.E

Substituting the last two equations into the first, we get
(c+1)↑3 (log(5))↑2 =  d log(2)log(3).
Hence c+1 = CUBEROOT[d log(2) log(3) / log↑2(5)].

For reasons which will become apparent soon, we will transform this slightly into


c+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(5)

The nicely symmetric equations for a+1 and b+1 turn out to be:

.B1


a+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(2)

b+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(3)

.E

Viewed in this way, we can rewrite our equation from the k=2 case into the
same kind of expression, namely:

.B1

a+1 = SQUAREROOT[ d log(2) log(3) ] / log(2)

b+1 = SQUAREROOT[ d log(2) log(3) ] / log(3)

.E

Again the general pattern seems to be evident:

.B1

a↓i+1 = K↑t↑hROOT[ d log(2) log(3)...log(p↓k) ] / log(p↓i)

.E

As in the k=2 case, the equations for a,b,c have real correspondence
to the optimal integral values of the exponents.


.SKIP TO COLUMN 1

⊗5↓_General Case_↓⊗*

We are now ready to consider the most general case, namely when
n = 2↑a↑[⊗71⊗*]3↑a↑[⊗72⊗*...]p↓k↑a↑[⊗7k⊗*].
By T1, we know that
d(n) = (a↓1+1)(a↓2+1)...(a↓[⊗7k⊗*]+1).
One generalization of our earlier work would indicate that minima of
n (for a given value of d) occur whenever

.SELECT 1

⊗5(T2)⊗* [for all i and j between 1 and k] (a↓i+1)/(a↓j+1) = log(p↓j)/log(p↓i).

This is really a set of k-1 equations in the k different variables a↓1,...,a↓k.
Using the formula for d which T1 provides, we can solve this system of equations
for each a↓i in terms only of d. The resulting formulae are:


⊗5(T3)⊗* [⊗6∀i≤k⊗*]  a↓i+1 = K↑t↑hROOT[ d log(2) log(3)...log(p↓k) ] / log(p↓i)

The proofs of T2 and T3 are left to the reader. 
⊗7(Hint: I can prove one of them given the other)⊗*.
Assuming them as true, we can actually compute the optimal values for n.
It will simplify matters again to consider only log(n) for the moment.
[note: SIGMA↓i(...) means "the sum, from i=1 to i=k, of ..."] Now

.B1 SELECT 1


log(n) = a↓1log(2) + a↓2log(3) +...+ a↓klog(p↓k)

= SIGMA↓i[log(p↓i) a↓i]

= SIGMA↓i[log(p↓i)((K↑t↑hROOT[ d log(2) log(3)...log(p↓k) ]/log(p↓i)) -  1)]

= SIGMA↓i[K↑t↑hROOT( d log(2) log(3)...log(p↓k) )  -  log(p↓i)]

= k[K↑t↑hROOT( d log(2) log(3)...log(p↓k))] -  SIGMA↓i[log(p↓i)]

If we let F↓k represent the product of the first k primes, then this says

↓n ↓= ↓e[k K↑t↑hROOT(d) K↑t↑hROOT(log(2)log(3)...log(p↓k))]/F↓k.

If we let G↓k be ↓e[k K↑t↑hROOT(log(2)...log(p↓k))], then this becomes

⊗5(T4)⊗* ↓n ↓= ↓G↓[⊗7k⊗*][K↑t↑hROOT(d)]/F↓k].

.E

So by tabulating G↓k and F↓k, we can efficiently compute the ideal value
for n (and for each a↓i) given a desired d and allowable k.
Notice that if we are allowed more and more distinct prime factors,
that is, as k grows, the real-valued exponents a↓i get smaller and smaller,
until finally they become negative, and we have broken all ties to reality.
Empirically, the ideal value obtained when no exponent is allowed to be
below 0.5 is both close to, and slightly lower than, any intergral solution.

Of course this is not satisfactory; what we now need is a formula which
tells us, for a given d, how many distinct prime factors any n must
have, in order to have d divisors. That is, we would like to know k as a 
function of d.
As it is, k increases like log(log(n)), hence is easy to estimate empirically.

.SKIP TO COLUMN 1

⊗5↓_An even stronger claim_↓⊗*

There is another route out of this problem, namely if the following were true:

⊗5(T5)⊗* The set M of maximally divisible numbers coincides precisely
with the set of integers obtained in the following manner:

.B1 INDENT 5,5,0

(1) For each natural number d, use T3 to compute the optimal exponents for
n(d,k), with k as large as possible such that no a↓i is below 0.5

(2) Round each exponent to the nearest integer, and compute the corresponding n.
Add this n to the set.

.E

There is probably a nice closed-form formula for such numbers, a sort of
"compiled" version of T3 and T5. This is then the desired characterization
of M.
Exhaustive search has in fact confirmed T5 for all d below 1500.
T5 has the advantage of being intuitively clear. Perhaps its proof will turn
out to be nontrivial or nonexistent. I leave it as "AM's conjecture".
This is so far the only piece of interesting mathematics, previously unknown, 
that was directly motivated by AM (a computer program, written by Lenat, which
proposes new and supposedly interesting concepts to investigate).

For example: consider d=1344. The largest that k can be without T3 calling for
⊗6a↓k < 0.5⊗* is k=7. For this d and k, T3 predicts exponents
5.9, 3.3, 2.0, 1.4, 1.0, 0.9, and 0.7.
Rounding this off, we get 6, 3, 2, 1, 1, 1, 1. Next we compute
2↑63↑35↑27↑111↑113↑117↑1. This is 735,134,400. T1 tells us that this has
in fact precisely 1344 divisors (coincidence). Exhaustive search tells us that
no smaller n has that many divisors (this is a verification of T5).
Incidentally, the ideal value for n (for this k and d value) is 603,696,064.
Notice that it is close to, and less than, the best possible n with 1344 divisors.

Another such "rounded-exponent" number is
n=2⊗88⊗*3⊗85⊗*5⊗83⊗*7⊗82⊗*11⊗82⊗*13⊗81⊗*17⊗81⊗*19⊗81⊗*23⊗81⊗*29⊗81⊗*31⊗81⊗*37⊗81⊗*41⊗81⊗*43⊗81⊗*47⊗81⊗*53⊗81⊗*.
The progression of its exponents+1 (9 6 4 3 3 2 2 2 2 2 2 2 2 2 2 2)
is  about as  close  as one  can  get  to satisfying the  "logarithm"
constraint.
By that I mean that 9/6 is close to log(3)/log(2); that 2/2 is close to
log(47)/log(43), etc.  Changing any exponent by plus or minus 1 would make
those ratios worse than they are.
This  number n is about 25 billion, and has about 4 million divisors.
The AM conjecture is that there is no smaller number with that many divisors.
Incidentally, the average number in the neighborhood of n has about 
2↑[loglog n] divisors (about 9, for this n).

.SKIP TO COLUMN 1
⊗5↓_New Questions and Tasks_↓⊗*


Supply proof of T1 (see standard Number Theory text if stuck).

Supply proof that the "ideal" exponents have real significance for the
special case of k=2. 

Supply proof of this fact for k=3 or general case.

Supply proof of T2 (difficult).

Supply proof of T3 (messy but not too hard, given T2).

Tabulate the constants G↓k and F↓k (as used in T4), and notice new
regularities.

Find k(d). That is, given a desired number of divisors d, how many distinct
prime divisors will be possessed by the smallest number with d divisors.

Prove T5. Or, establish it empirically for large d. Or, prove it for
special cases.

Devise a calculus of these maximally-divisible numbers.
What about their product? sum?  If the quotient of two members of M
is divisible by 2, then there is a high probability that it is in M.

Empirically, ⊗6if xεM, then there is a high probability that d(x)εM.⊗*
Why? What is the significance of this? Can you use it to find new, large
members of M?

Can M be used to shorten proofs about the normal order of d(n)?
Can many deep conjectures be posed cheaply (as with primes) by asking
about relations involving addition and M?
(e.g., every number x is the sum of at most log(x) members of M)

Can members of M be used to speed up factoring algorithms?
How about using M to find large primes? Prime pairs? What is the
neighborhood of members of M like?